import gmpy2
from Crypto.Util.number import *
import libnum


n= 91114608755767875397025248210560683973533675637566993209399108116240081659500790390575906252267023615840292492773766671189651089914991257867566729003319541603344851338176772246217816483241790638062022346670553330202152637164677531367945607415342933228291647071075912271352596789555183874554313155417444988443
c= 47661203935878085549688440399422137180912028183358383845019724110167943938970200917418709069329432123095001276291212957892519213289156569464653786224398389431983119101768114069506066623426023265465250672723636042963542965272847513200667281201362507839872514614627751330400003420311801907931412805212549478900

e = 65537


q_near = gmpy2.iroot(n,2)[0]
while n%q_near!=0:
    q_near=gmpy2.next_prime(q_near)
q = q_near
p = n//q
print(f"p={p}")
print(f"q={q}")
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(m)

import libnum
m1=m*libnum.invmod(-1,p)%p
print("m1=",m1)
for i in range(p,q):
    m = m*i%q
m2 = m * gmpy2.invert(-1,q) %q
print(m2)
flag = libnum.solve_crt([m1,m2],[p,q])
print(flag)
print(long_to_bytes(flag))
